class Solution:
    def isBipartite(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: bool
        """
        WHITE, BLACK = range(2)
        if not graph:
            return True
        def dfs(node, color=WHITE):
            if node in colormap:
                return colormap[node] == color
            # assign color to node
            colormap[node] = color
            # toggle color
            color = BLACK if color == WHITE else WHITE
            # check following nodes
            return all(dfs(neighbor, color) for neighbor in graph[node])
        colormap = {}
        # check graph nodes
        return all(dfs(node) for node in range(len(graph)) if node not in colormap)

    def isBipartite1(self, graph):
        def validate(color, node):
            if colors[node]!=0:
                return colors[node]==color
            colors[node] = color
            for nextnode in graph[node]:
                if not validate(-1*color, nextnode):
                    return False
            return True

        if not graph:
            return False
        colors = [0]*len(graph)
        for cur, items in enumerate(graph):
            if colors[cur] == 0 and not validate(1, cur):
                return False
        return True

s=Solution()
print(s.isBipartite([[1,3], [0,2], [1,3], [0,2]]))

